Search results for "strongly connected component"
showing 6 items of 6 documents
A Generalization of Girod’s Bidirectional Decoding Method to Codes with a Finite Deciphering Delay
2012
In this paper we generalize an encoding method due to Girod (cf. [6]) using prefix codes, that allows a bidirectional decoding of the encoded messages. In particular we generalize it to any finite alphabet A, to any operation defined on A, to any code with finite deciphering delay and to any key x ∈ A+ , on a length depending on the deciphering delay. We moreover define, as in [4], a deterministic transducer for such generalized method. We prove that, fixed a code X ∈ A* with finite deciphering delay and a key x ∈ A *, the transducers associated to different operations are isomorphic as unlabelled graphs. We also prove that, for a fixed code X with finite deciphering delay, transducers asso…
INTERVAL-BASED TRACING OF STRANGE ATTRACTORS
2006
The method described here relies on interval arithmetic and graph theory to compute guaranteed coverings of strange attractors like Hénon attractor. It copes with infinite intervals, using either a geometric method or a new directed projective interval arithmetic.
Theory of Computation, Fuzziness and a physics of the immaterial
2013
In this paper we advance three clear-cut proposals as a contribution to the discussion on the role of notions of Computation and Fuzziness as a bridge between Hard and Soft Sciences. We suggest that an important difference between the two great fami- lies of science lies in their subject or research having a grounding in nature or not, and that Theory of Computation is a glaring exception to this classifi- cation, being a textbook hard science but dealing with the immaterial. We further advance that such unicity is strongly connected with Church-Turing thesis, and discuss about the role of Computation and Fuzziness as pillars of immaterial sciences
A Generalization of Girod's Bidirectional Decoding Method to Codes with a Finite Deciphering Delay
2012
Girod’s encoding method has been introduced in order to efficiently decode from both directions messages encoded by using finite prefix codes. In the present paper, we generalize this method to finite codes with a finite deciphering delay. In particular, we show that our decoding algorithm can be realized by a deterministic finite transducer. We also investigate some properties of the underlying unlabeled graph.
On modal mu-calculus over finite graphs with bounded strongly connected components.
2010
For every positive integer k we consider the class SCCk of all finite graphs whose strongly connected components have size at most k. We show that for every k, the Modal mu-Calculus fixpoint hierarchy on SCCk collapses to the level Delta2, but not to Comp(Sigma1,Pi1) (compositions of formulas of level Sigma1 and Pi1). This contrasts with the class of all graphs, where Delta2=Comp(Sigma1,Pi1).
Geography versus topology in the European Ownership Network
2011
In this paper, we investigate the network of ownership relationships among European firms and its embedding in the geographical space. We carry out a detailed analysis of geographical distances between pairs of nodes, connected by edges or by shortest paths of varying length. In particular, we study the relation between geographical distance and network distance in comparison with a random spatial network model. While the distribution of geographical distance can be fairly well reproduced, important deviations appear in the network distance and in the size of the largest strongly connected component. Our results show that geographical factors allow us to capture several features of the netw…